#include <stdio.h>
#include <iostream>
#include <assert.h>
typedef int DListNodeType;

typedef struct DListNode
{
    DListNodeType data;
    struct DListNode* next;
    struct DListNode* prev;
}DListNode;

DListNode* BuyDListNode(DListNodeType x)
{
    DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
    if(newnode == nullptr)
    {
        std::cout << "malloc fail!" << std::endl;
        exit(-1);
    }
    newnode->data = x;
    newnode->next = nullptr;
    newnode->prev = nullptr;
}

DListNode* DListInit()
{
    DListNode* phead = BuyDListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

void DListNodeDestory(DListNode* phead)
{
    assert(phead);
    DListNode* cur = phead->next;
    DListNode* next = cur->next;

    while(cur != phead)
    {
        free(cur);
        cur = next;
        next = next->next;
    }
    free(phead);
    phead = nullptr;
}


void DListNodePrint(DListNode* phead)
{
    DListNode* cur = phead->next;

    while(cur != phead)
    {
        std::cout << cur->data << std::endl;
        cur = cur->next;
    }
    std::cout << "NULL\n";
}

DListNode* DListNodeFind(DListNode* phead, DListNodeType x)
{
    DListNode* cur = phead->next;

    while(cur != phead)
    {
        if(cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return nullptr;
}

void DListNodePushFront(DListNode* phead, DListNodeType x)
{
    assert(phead);

    DListNode* newnode = BuyDListNode(x);
    DListNode* front = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = front;
    front->prev = newnode;
}

void DListNodePushFront(DListNode* phead, DListNodeType x)
{
    assert(phead);
    DListNode* newnode = BuyDListNode(x);
    DListNode* tail = phead->prev;

    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->next = newnode;
}

void DListNodeInsert(DListNode* pos, DListNodeType x)
{
    assert(pos);
    DListNode* before = pos->prev;
    DListNode* newnode = BuyDListNode(x);

    before->next = newnode;
    newnode->prev = before;
    newnode->next = pos;
    pos->prev = newnode;
}

void DListNodePopFront(DListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);

    DListNode* front = phead->next;
    DListNode* newfront = front->next;
    phead->next = newfront;
    newfront->prev = phead;
    free(front);
}

void DListNodePopBack(DListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);

    DListNode* tail = phead->prev;
    DListNode* newtail = tail->prev;
    
    newtail->next = phead;
    phead->prev = newtail;
    free(tail);
}

void DListNodePop(DListNode* pos)
{
    assert(pos);

    DListNode* before = pos->prev;
    DListNode* after = pos->next;
    before->next = after;
    after->prev = before;
    free(pos);
}

bool DListNodeEmpty(DListNode* phead)
{
    assert(phead);
    if(phead->next == phead) return true;
    return false;
}

int DListNodeSize(DListNode* phead)
{
    assert(phead);
    DListNode* cur = phead->next;
    int size = 0;
    while(cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}